//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_ITERATOR_FILTER_H_
#define _BUOLA_ITERATOR_FILTER_H_

#include <buola/iterator/facade.h>
#include <buola/iterator/range.h>
#include <buola/functors/predicates/unary.h>

namespace buola {

///\addtogroup iterators
///@{

///\cond
template<typename tSub,typename tPred>
class IFilter;

namespace detail {

    template<typename tSub,typename tPred>
    struct MIteratorFilter
    {
        typedef OConditional<QIteratorSupports<tSub,std::random_access_iterator_tag>,
                    std::bidirectional_iterator_tag,OIteratorCategory<tSub>> TCategory;
        typedef IFacade<IFilter<tSub,tPred>,TCategory,typename std::iterator_traits<tSub>::value_type,typename
                std::iterator_traits<tSub>::reference,typename std::iterator_traits<tSub>::difference_type> TFacade;
    };

/*namespace detail*/ }
///\endcond

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
/// iterator filter adaptor
///
/// Adapts another iterator (the underlying iterator) so that elements that don't match a certain predicate are
/// skipped when iterating.
///
/// So that it can safely skip elements and know where to stop, it must hold a copy of the end iterator. For this
/// reason, a single iterator can't be filtered, and no filter_iterator function is provided
///
/// \tparam tSub the underlying iterator type
/// \tparam tPred the type of the predicate function or function object. It must take as argument the type returned by
///         dereferencing the underlying operator and return a type convertible to boolean
///
/// For an example, see the helper function \ref filter_range
///
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename tSub,typename tPred>
class IFilter : public detail::MIteratorFilter<tSub,tPred>::TFacade
{
    typedef typename detail::MIteratorFilter<tSub,tPred>::TFacade TFacade;
    friend TFacade;

public:
    ///default constructor (invalid iterator)
    IFilter()=default;

    ///initializes the iterator from an underlying iterator \p pSub, a predicate \p pPred and an end iterator
    IFilter(const tSub &pSub,const tPred &pPred,const tSub &pEnd)
        :   mSub(pSub)
        ,   mPred(pPred)
        ,   mEnd(pEnd)
    {
        while(mSub!=mEnd&&!mPred(*mSub))
            ++mSub;
    }

    ///allows access to the underlying iterator
    const tSub &Sub()   {   return mSub;    }

private:
    ///returns the result of dereferencing the underlying iterator
    typename TFacade::reference Dereference() const
    {
        return *mSub;
    }

    ///increments the underlying iterator
    void Increment()
    {
        ++mSub;
        while(mSub!=mEnd&&!mPred(*mSub))
            ++mSub;
    }

    ///decrements the underlying iterator
    void Decrement()
    {
        do
        {
            --mSub;
        } while(!mPred(*mSub));
    }

    ///returns true if the two underlying iterators contain the same value
    ///
    ///It is OK to use a generic template parameter, since it will only be called for compatible iterators.
    template<typename tO>
    bool Equal(const tO &pO) const
    {
        return mSub==pO.mSub;
    }

    tSub mSub;
    tPred mPred;
    tSub mEnd;
};

///\name Filter
//@{

///returns an \ref IFilter object pointing to the beginning of the range \p pRange
///
///\param pRange the range to which the filtering will be applied
///\param pPred the predicate for filtering. Only elements for which it evaluates to `true` will be included in the range
///
///It will actually point to the first element which matches the given predicate.
template<typename tRange,typename tPred>
inline IFilter<ORangeIterator<tRange>,tPred> filter_begin(tRange &&pRange,const tPred &pPred)
{
    return {range_begin(pRange),pPred,range_end(pRange)};
}

///returns an \ref IFilter object pointing past the end of the range \p pRange
///
///\param pRange the range to which the filtering will be applied
///\param pPred the predicate for filtering. Only elements for which it evaluates to `true` will be included in the range
template<typename tRange,typename tPred>
inline IFilter<ORangeIterator<tRange>,tPred> filter_end(tRange &&pRange,const tPred &pPred)
{
    return {range_end(pRange),pPred,range_end(pRange)};
}

///returns a range that can be used to access the elements in the range [\p pB,\p pE), filtered by \p pPred
///
///\param pB the beginning of the range to filter
///\param pE the end of the range to filter
template<typename tSub,typename tPred>
inline CRange<IFilter<tSub,tPred>> filter_range(const tSub &pB,const tSub &pE,const tPred &pPred)
{
    return {{pB,pPred,pE},{pE,pPred,pE}};
}

///returns a range that can be used to access the elements in \p pRange, filtered by \p pPred
///
///\param pRange the range to which the filtering will be applied
///\param pPred the predicate for filtering. Only elements for which it evaluates to `true` will be included in the range
///
///It is equivalent to `filter_range(range_begin(pRange),range_end(pRange),pFunc)`
///
///For example,
///~~~~~~~~~~~~~~~~
///void print_multiples_of(const std::vector<int> &pVector,int pN)
///{
///    auto lRange=filter_range(pVector,[pN](int pI)->bool{return pI%pN==0});
///    std::copy(lRange.begin(),lRange.end(),io::ITextWriter<int>(gOut," "));
///}
///~~~~~~~~~~~~~~~~
///would print the elements in pVector which are a multiple of pN.
template<typename tRange,typename tPred>
inline auto filter_range(tRange &&pR,const tPred &pPred) -> decltype(filter_range(range_begin(pR),range_end(pR),pPred))
{
    return filter_range(range_begin(pR),range_end(pR),pPred);
}

///\cond
namespace detail {

    template<typename tPred>
    class CFilterForwarder
    {
    public:
        CFilterForwarder(const tPred &pPred)
            :   mPred(pPred)
        {}

        const tPred &Pred() const {   return mPred;   }

    private:
        const tPred &mPred;
    };


    template<typename tRange,typename tPred>
    auto operator|(const tRange &pR,const CFilterForwarder<tPred> &pF) -> decltype(filter_range(pR,pF.Pred()))
    {
        return filter_range(pR,pF.Pred());
    }

/*namespace detail*/ }
///\endcond

///returns an object that can be used to filter ranges
///
///\param pPred the predicate used for filtering
///
///The only safe way to use the returned object is to use operator| to filter a range, as in:
///
///~~~~~~~~
///for(char i : "ABC" | filter(!fn::equal_to('B')))
///    msg_info() << i;
///~~~~~~~~
///
///which will print `AC`
template<typename tPred>
detail::CFilterForwarder<tPred> filter(const tPred &pPred)
{
    return {pPred};
}

namespace fn {
    ///returns the range filtered by the unary predicate \p pTransform
    template<typename tRange,typename tPred>
    OEnableIfTag<tPred,GUnaryPredicate,CRange<IFilter<ORangeIterator<tRange>,tPred>>>
    operator|(const tRange &pRange,const tPred &pPred)
    {
        return filter_range(pRange,pPred);
    }
/*namespace fn*/ }

//@}

///@}

/*namespace buola*/ }

#endif
